import java.util.ArrayList;

/**
 * 队列+宽搜
 * 662、二叉树最大宽度
 */
public class Day16 {
     public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public int widthOfBinaryTree(TreeNode root) {
        //使用Pair<TreeNode,Integer>来存储节点和对应的下标的关系,这里的下标是像堆一样进行计算,比如:根为x,那么左为2x,右为2x+1 (根从1下标开始)
        // Pair<TreeNode,Integer>是一种映射关系的存储为一个整体
        List<Pair<TreeNode, Integer>> queue = new ArrayList<>();
        queue.add(new Pair<TreeNode,Integer>(root,1)); // 根节点从1开始计数
        int ret = 0; // 统计最长的宽度

        while(!queue.isEmpty()) {
            // 每次进入while循环中就是一个新的一层，要先来计算这一层的最大宽度
            Pair<TreeNode,Integer> t1 = queue.get(0); // 这个是使用数组进行模拟的，所以可以根据下标直接得到对应的Pair对象
            Pair<TreeNode,Integer> t2 = queue.get(queue.size() - 1);
            ret = Math.max(ret,t2.getValue() - t1.getValue() + 1); // t2.getValue() - t1.getValue() + 1这个得到的就是这一层的宽度

            // 计算完宽度，进入下一层
            List<Pair<TreeNode,Integer>> tmp = new ArrayList<>();
            for(Pair<TreeNode,Integer> t : queue) {
                TreeNode node = t.getKey();
                int index = t.getValue();
                if(node.left != null) {
                    tmp.add(new Pair<TreeNode,Integer>(node.left,index * 2));
                }
                if(node.right != null) {
                    tmp.add(new Pair<TreeNode,Integer>(node.right,index * 2 + 1));
                }
            }
            queue = tmp;
        }
        return ret;
    }
}
